144
144

question

######
eye 144

######
favorite 0

######
comment 0

Speaker : Jordan Ellenberg

Topics: Mathematics, lecture

288
288

question

######
eye 288

######
favorite 0

######
comment 0

Speaker : Carlos Kenig

Topics: Mathematics, lecture

210
210

question

######
eye 210

######
favorite 0

######
comment 0

Speaker: Michael Gage http://www.msri.org/calendar/workshops/WorkshopInfo/284/show_workshop

Topics: Mathematics, lecture

307
307

question

######
eye 307

######
favorite 0

######
comment 0

Speaker : Persi Diaconis Keywords : Analysis of algorithms; poissonization; conditioned limit theory; Lecams method; Bayes theory; definettis theorem. Abstract : Poissonization can be abstracted to a wide ranging method for randomizing a perimeter to make components independent. This allows us to handle exponential structures, random matrices and much else. There are many ways of derandomizing. I will feature Bayes theorem and Lecams method.

Topics: Mathematics, lecture

107
107

question

######
eye 107

######
favorite 0

######
comment 0

Speaker : Chris Skinner

Topics: Mathematics, lecture

236
236

question

######
eye 236

######
favorite 0

######
comment 0

Speaker : Stafford

Topics: Mathematics, lecture

251
251

question

######
eye 251

######
favorite 0

######
comment 0

Speaker : Carlos Kenig

Topics: Mathematics, lecture

281
281

question

######
eye 281

######
favorite 0

######
comment 0

Speaker : Marcos Kiwi Keywords : Analysis of algorithms; longest common subsequence; Sankoff & Mainville conjecture; longest increasing sequence; random graphs. Abstract : We consider the length L of the longest common subsequence of two randomly, uniformly and independently chosen n. We prove conjecture of Sankoff and Mainville from the early 80's concerning the asympotic (in k) behavior limiting constant.

Topics: Mathematics, lecture

249
249

question

######
eye 249

######
favorite 0

######
comment 0

Speaker: Francis Su

Topics: Mathematics, lecture

306
306

question

######
eye 306

######
favorite 0

######
comment 0

Speaker : Bridgitte Vallee Keywords: Analysis of algorithms; Euclidean algorithms; continued fraction expansion; dynamical systems; transfer operators; central and local limit theorems. Abstract: We show how dynamical analysis (=analysis of algorithms and dynamical systems) applies to the Euclidean context and provides a very precise distributional analysis of Euclidean algorithms. It proves that, in a strong sense, Euclidean algorithms are Gaussian.

Topics: Mathematics, lecture

244
244

question

######
eye 244

######
favorite 0

######
comment 0

Speaker: Francis Su

Topics: Mathematics, lecture

333
333

question

######
eye 333

######
favorite 0

######
comment 0

NOTE: no sound in first 20 seconds Speaker : Bruno Salvy Keywords : Analysis of algorithms; Grobner bases; generic complexity; coalescence of saddle-points. Abstract : While the computation of Grobner bases is known to be an exsapace complete problem, the generic behavior of the algorithms for their bases and analyze precisely the best algorithm currently known.

Topics: Mathematics, lecture

203
203

question

######
eye 203

######
favorite 0

######
comment 0

Speaker : Helmut Prodinger Keywords: Analysis of algorithms; redundant number representation; simple joint sparse form; non-adjacent form.

Topics: Mathematics, lecture

167
167

question

######
eye 167

######
favorite 0

######
comment 0

Speaker : Vincent Puyhaubert Keywords : Analysis of algorithms; analytic urns, stable limit law, Mellin transform, Fubini theorem, Event generating function, Convergence in distribution Abstract : We present an analytic approach to urn models. The method is the same as in Flajolet-Gabarro-Pekari wich consists in enumerating all events starting from an initial urn. A PDE is obtained for the generating function wich is solved by method of characteristics. Then the analytic study of the GF derives...

Topics: Mathematics, lecture

731
731

question

######
eye 731

######
favorite 0

######
comment 0

Speaker : Greg Sorkin Keywords : Analysis of algorithms; average-case analysis; branching processes; Brownian motion; phase transition; scaling window; constraint satisfaction; satisfiability. Abstract : A maximum cut in a random graph below the giant component threshold can be found in linear space and linear expected time by a simple algorithm. The same algorithm solves the more general class Max 2-CSP of weighted binary 2-variable constraint satisfaction problems, which includes weighted Max...

Topics: Mathematics, lecture

235
235

question

######
eye 235

######
favorite 0

######
comment 0

Speaker : Richard Taylor

Topics: Mathematics, lecture

172
172

question

######
eye 172

######
favorite 0

######
comment 0

Speaker : Kazuhiro Fujiwara

Topics: Mathematics, lecture

173
173

question

######
eye 173

######
favorite 0

######
comment 0

Speaker : Bernd Sturmfels

Topics: Mathematics, lecture

130
130

question

######
eye 130

######
favorite 0

######
comment 0

Speaker : Paul Vojta The end of this lecture was clipped during taping.

Topics: Mathematics, lecture

461
461

question

######
eye 461

######
favorite 0

######
comment 0

Speaker : Matthias Flach

Topics: Mathematics, lecture

243
243

question

######
eye 243

######
favorite 0

######
comment 0

Speaker : Serap Savari

Topics: Mathematics, lecture

183
183

question

######
eye 183

######
favorite 0

######
comment 0

Speaker : Alberto Apostolico

Topics: Mathematics, lecture

357
357

question

######
eye 357

######
favorite 0

######
comment 0

Speaker : Mark Ward Keywords : Analysis of algorithms; data compression; suffix trees; tries; Poissonization; Mellin transform; redundancy; pattern matching. Abstract : We present the asympotics of the distribution and moments of Mn, the matching multiplicity parameter, for tries constructed on independent strings. We also present work-in-progress that Mn for suffix trees has the same asympotic distribution and moments.

Topics: Mathematics, lecture

272
272

question

######
eye 272

######
favorite 0

######
comment 0

Speaker : Bridgitte Chauvin

Topics: Mathematics, lecture

226
226

question

######
eye 226

######
favorite 0

######
comment 0

Speaker : Predrag Jelenkovic Keywords: Analysis of algorithms;persistent-access-caching, least-recently-used caching, least-frequently-used caching, move-to-front searching, generalized Zipf's law distributions, heavy-tailed distributions, Web caching, cache fault probability, average-case analysis, variable page sizes, long-range dependence Abstract: The most popular caching algorithms in practice are based on the Least-Recently-Used (LRU) cache replacement rule that possesses many desirable...

Topics: Mathematics, lecture

370
370

question

######
eye 370

######
favorite 0

######
comment 0

Speaker : Tatiana Toro

Topics: Mathematics, lecture

342
342

question

######
eye 342

######
favorite 0

######
comment 0

Speaker : Chuck Knessl Keywords : Analysis of algorithms; Asympotics; WKB method; digital trees; quicksort; binary search trees; matched asympotic expansions. Abstract : We apply singular perturbation techniques to the analysis of algorithms and to trees. Examples include digital tress, binary search trees and quicksort algorithm.

Topics: Mathematics, lecture

188
188

question

######
eye 188

######
favorite 0

######
comment 0

Speaker : Christophe Breuil

Topics: Mathematics, lecture

378
378

question

######
eye 378

######
favorite 0

######
comment 0

Speaker : Fred Diamond

Topics: Mathematics, lecture

125
125

question

######
eye 125

######
favorite 0

######
comment 0

Speaker: Francis Su

Topics: Mathematics, lecture

215
215

question

######
eye 215

######
favorite 0

######
comment 0

Speaker : Daniele Gardy Keywords: Analysis of algorithms; Boolean function representation; probability distributions on boolean functions. Abstract: We study several tree representations of boolean functions, to take into account commutativity or associativity of the boolean operators. We show how we can define related probability distributions on boonlean functions, and study some relationships between these distributions. We also consider the relation to boolean function complexity.

Topics: Mathematics, lecture

116
116

question

######
eye 116

######
favorite 0

######
comment 0

Speaker : Julien Fayolle

Topics: Mathematics, lecture

340
340

question

######
eye 340

######
favorite 0

######
comment 0

Speaker : Carl Pomerance

Topics: Mathematics, lecture

172
172

question

######
eye 172

######
favorite 0

######
comment 0

Speaker : Chris Skinner

Topics: Mathematics, lecture

350
350

question

######
eye 350

######
favorite 0

######
comment 0

Speaker : Jim Renegar

Topics: Mathematics, lecture

336
336

question

######
eye 336

######
favorite 0

######
comment 0

Speaker : Lou Van Den Dries

Topics: Mathematics, lecture

152
152

question

######
eye 152

######
favorite 0

######
comment 0

Speaker : Lou Van Den Dries

Topics: Mathematics, lecture

96
96

question

######
eye 96

######
favorite 0

######
comment 0

Speaker : Alex Wilkie

Topics: Mathematics, lecture

275
275

question

######
eye 275

######
favorite 0

######
comment 0

Speaker : Ana Vargas Note: Last two minutes of lecture were cutoff on the original tape.

Topics: Mathematics, lecture

229
229

question

######
eye 229

######
favorite 0

######
comment 0

Speaker : Ana Vargas

Topics: Mathematics, lecture

176
176

question

######
eye 176

######
favorite 0

######
comment 0

Speaker : Gadiel Seroussi

Topics: Mathematics, lecture

226
226

question

######
eye 226

######
favorite 0

######
comment 0

Speaker : Tatiana Toro

Topics: Mathematics, lecture

320
320

question

######
eye 320

######
favorite 0

######
comment 0

Speaker : Tatiana Toro

Topics: Mathematics, lecture

238
238

question

######
eye 238

######
favorite 0

######
comment 0

Speaker : Matzat

Topics: Mathematics, lecture

209
209

question

######
eye 209

######
favorite 0

######
comment 0

Speaker : Stafford

Topics: Mathematics, lecture

194
194

question

######
eye 194

######
favorite 0

######
comment 0

Speaker : Alfredo Viola Keywords: Analysis of algorithms; hashing; linear probing; robin hood;exact distribution; buckets; individual displacements. Abstract: We present the distribution of the individual displacements in linear probing hashing with buckets using the robin hood heuristic. In the derivation we present anew sequence of numbers that are very useful study truncated recurrences. We study full tables and also we give results for fixed values of the size of the table and number...

Topics: Mathematics, lecture

321
321

question

######
eye 321

######
favorite 0

######
comment 0

Speaker : Edward Bierstone

Topics: Mathematics, lecture

296
296

question

######
eye 296

######
favorite 0

######
comment 0

Speaker : Bernard Gittenberger Keywords: Analysis of algorithms; systems of functions; normal limit log, combinatorial enumeration; quasi-power theorem. Abstract: When counting combinatorial objects which are defined recursively, this leads naturally to functional equations for the generating functions. We present several examples in combinatorial enumeration where the generating function satisfies a functional equation of the form $F(z,u)=Q(z,u,F(z,u))$. Various cases appear $F$ and $Q$ are...

Topics: Mathematics, lecture

117
117

question

######
eye 117

######
favorite 0

######
comment 0

Speaker : H.K. Hwang Keywords : Analysis of algorithms;point quadtrees, profile, limit distributions, variance, bimodality, convergence of all moments. Abstract : Limit theorems for profile in random point quadtrees are presented. Special features include: unimodal mean but bimodal variance, the range for convergence in distribution is different from that for convergence of all moments, the limit law does not exist in a small range, etc. The phenomena are not.

Topics: Mathematics, lecture

497
497

question

######
eye 497

######
favorite 0

######
comment 0

Speaker : Hung-Hsi Wu

Topics: Mathematics, lecture